<!DOCTYPE html>
<html>

<head>
    <meta charset="utf-8">
    <title>Maxmilite</title>
    <link rel="icon" href="../icon.png" type="image/x-icon">
</head>

<link rel="stylesheet" href="../css/style-archive.css">

<canvas id="snow-flake-app"></canvas>
<script src="../js/snow-flake-app.js"></script>

<!-- <ul class="nav">
    <li style="width: 40%;">
        <div>
            <p style="font-size: xx-large;"><img src="../icon.png" height="40px" width="40px"
                    style="border-radius: 4px;">&nbsp;Maxmilite</p>
        </div>
    </li>
</ul> -->

<div class="main">
    <h1 style="text-align: center;">
        P3134 翻译
    </h1>
</div>

<script type="text/x-mathjax-config">
    MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}});
</script>
<script type="text/javascript" src="https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>

<xmp theme="united" style="display:none;" id="section">
### 题目描述

农夫 John 在他的谷仓里安装了一个非常不错的新挤奶机，但是这台挤奶机耗电太多了，有时候会让谷仓直接停电！这种事发生的太频繁了，以至于 Bessie 直接把谷仓的地图背过了，以便于可以在黑暗中找到谷仓的出口。她对于停电对于她快速离开谷仓的能力的影响非常好奇。比如说，她想知道她在黑暗中需要走多远来找到谷仓的出口。

谷仓里的路可以被描述为是一个简单的用几个顶点来表示的多边形，这些顶点可以按照顺时针被表示为 $(x_1, y_1)...(x_n, y_n)$（保证这些顶点连成的线没有交叉的情况）。这些点构成的边在水平轴（平行于 $x$ 轴）和竖直轴（平行于 $y$ 轴）之间交替出现。第一条边可以是任意一种类型。谷仓出口在坐标 $(x_1, y_1)$ 。Bessie 从谷仓内任意一个点 $(x_i, y_i)$ 开始走。她只可以沿着这些边走，要不然是顺时针，要不然就是逆时针，她的目标就是以最短距离抵达出口。当然，如果灯亮着的话这个事还算相对简单，因为她要不然顺时针要不然逆时针走，无所谓哪个方向的路程更短一点。

一天，谷仓突然停电了，导致 Bessie 受到惊吓、忘记了她站在哪个顶点。幸亏她还记得谷仓的准确地图，所以她可以四处走走，用她的触觉来弄清楚她的位置。不管什么时候，只要她站在一个顶点，那么她就可以感受到她在这个点的朝向角度，弄清楚这个点是不是出口。当她沿着谷仓的一个边走完的时候，她可以算出精确的边长。Bessie 决定用这么一个策略：她会顺时针沿着谷仓周围的边走，直到她知道了足够的角度和边、可以推断出她目前在的是哪个顶点。在那个顶点，她就可以轻易地弄清楚怎样以最短距离到达出口（要不然继续沿着顺时针走，要不然倒回去沿着逆时针走）。

请帮助 Bessie 算出在起点可以是任何一个顶点情况下，在最坏的情况下，她在黑暗中和亮着灯的时候到达出口的距离的差值（即找到差值的最大值）。

### 输入格式

第一行包括一个数字 $N (4 \leq N \leq 200)$ ，接下来 $N$ 行，每行包括两个数字，沿着顺时针表示顶点 $(x_i, y_i)$ &nbsp; $x_i, y_i \in [-10^5, 10^5]$ 。

### 输出格式

输出 Bessie 在最坏的情况下，她在黑暗中和亮着灯的时候到达出口的距离的差值（即找到差值的最大值）。

### 说明/提示

在这个样例中，Bessie 开始可以感觉到她沿着 90° 角站着，但是她辨别不出来她是在 $2, 3, 4$ 中的哪一个顶点。

在走了一条边以后，Bessie 要不然到了出口要不然就可以根据她走过的距离推断出她的位置。情况如下：

如果她从 $2$ 号点开始走，她需要在黑暗中走 $12$ 个单位，包括一个单位到达第三个点、十一个单位离开谷仓。同时，如果亮着灯，她可以只走 $10$ 个单位就离开谷仓。差值是 $2$ 。

如果从 $3$ 号点开始，她两种情况都要走 $11$ 个单位。

如果从 $4$ 号点开始走，她两种情况都要走 $1$ 个单位。

所以最坏情况差值是 $2$ 。
</xmp>


<script src="strapdown/v/0.2/strapdown.js"></script>

<div>
    <!-- Button Here -->
    <!-- Fixed Button 2021-04-18-->
    <a class="button" href="../archives.html" style="width: 40%; border-radius: 8px; margin-left: 30%; margin-top: 100px;  margin-bottom: 40px">
        <p style="font-size: 2vmax;">
            <<< Return to archive list </p>
    </a>
</div>

</html>